import matplotlib.pyplot as plt
import bisect
from random import random
from time import time

EPS = 1e-3

class Point:
    def __init__(self, x, y):
        self.x = float(x)
        self.y = float(y)
    def coords(self):
        return (self.x, self.y)
    def __sub__(self, p):
        return Point(self.x-p.x, self.y-p.y)
    def __lt__(self, p):
        return self.x < p.x if abs(self.y - p.y) < EPS else self.y > p.y
    def __eq__(self, p):
        return (abs(self.x - p.x) < EPS) and (abs(self.y - p.y) < EPS)
    def __str__(self):
        return("(%f, %f)" % (self.x, self.y))
    def __repr__(self):
        return(self.__str__())

class Segment:
    def __init__(self, p1, p2):
        if p1 < p2:
            self.upper, self.lower = p1, p2
        else:
            self.upper, self.lower = p2, p1
    def __str__(self):
        return("[%s - %s]" % (str(self.upper), str(self.lower)))
    def __repr__(self):
        return(self.__str__())

def line_line_intersection(p1, p2, p3, p4):
    x1, y1 = p1.x, p1.y
    x2, y2 = p2.x, p2.y
    x3, y3 = p3.x, p3.y
    x4, y4 = p4.x, p4.y

    denominator = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
    if abs(denominator) < 1e-3:
        return (False, p1)

    px = (x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4)
    px /= denominator
    py = (x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4)
    py /= denominator

    if between(px, x1, x2) and between(px, x3, x4) and \
       between(py, y1, y2) and between(py, y3, y4):
        p = Point(px, py)
        return (True, p)
    else:
        return (False, p1)

def intersection_point(seg1, seg2):
    p1 = seg1.upper
    p2 = seg1.lower
    p3 = seg2.upper
    p4 = seg2.lower
    result, point = line_line_intersection(p1, p2, p3, p4)
    if result:
        return point
    return -1

def flecha(p1, p2, c='b'):
    dx = p2.x - p1.x
    dy = p2.y - p1.y
    plt.arrow(p1.x, p1.y, dx, dy, color=c)

def between(x, x1, x2):
    if x1 > x2:
        x1, x2 = x2, x1
    if x1 < x and x < x2:
        return True
    return False

def cross_product(a, b):
    return (a.x * b.y) - (a.y * b.x)

def inside(point, segment):
    x, y = point.coords()
    x1, y1 = segment.upper.coords()
    x2, y2 = segment.lower.coords()
    # Veo si estan alineados. TODO: Deberia hacer un epsilon proporcional.
    if abs(cross_product(segment.upper-segment.lower, point-segment.lower)) < EPS:
        if between(x, x1, x2) and between(y, y1, y2):
            return True
    return False

def y_intersection(seg, y): #TODO esto no se que hace para segmentos vert o horiz
    x1, y1 = seg.upper.coords()
    x2, y2 = seg.lower.coords()
    return x1 + ((y1-y)/(y1-y2))*(x2-x1)



#for i in range(0, len(puntos), 2):
#    for j in range(i+2, len(puntos), 2):
#        intersecan, p = line_line_intersection(puntos[i], puntos[i+1], puntos[j], puntos[j+1])
#        if intersecan:
#            intersecciones.append(p)

#for i in range(0, len(puntos), 2):
#    flecha(puntos[i], puntos[i+1])

#for pi in intersecciones:
#    plt.plot(pi.x, pi.y, 'ro')

#plt.xlim(x1-0.1*dx, x2+0.1*dx)
#plt.ylim(y1-0.1*dy, y2+0.1*dy)
#print("Time: %f" % (end-start))
#plt.show()
